#include <cstdio>
#include <vector>
#include <unordered_set>
#include <stdexcept>

#define INF -1
using namespace std;

struct DijkstraResult 
{
    // 源节点
    int node;

    /**
     * dist[i]表示节点node到节点i的最短路径长度
     */
    vector<int> dist;
    /**
     * prev是一个辅助数组，prev[i]表示节点i的前驱节点，这些信息可以求解出源节点到其他所有节点的路径
     */
    vector<int> prev;
};

/**
 * 求源节点到图中其他所有节点的最短路径和路径信息
 * 保证：
 * - graph是一个二维矩阵且长度和宽度相等，INF表示不可达
 * - node ∈ [0, graph.size() - 1]
 * 
 * @param graph 有向带权图的邻接矩阵
 * @param node 源节点
 * @return 源节点到图中其他所有节点的最短路径和路径信息
 */
DijkstraResult dijkstra(vector<vector<int>>& graph, int node)
{
    int n = graph.size();
    /**
     * dist[i]表示节点node到节点i的最短路径长度
     */
    vector<int> dist(n, -1);
    dist[node] = 0;

    /**
     * prev是一个辅助数组，prev[i]表示节点i的前驱节点
     */
    vector<int> prev(n, -1);
    unordered_set<int> s;
    s.insert(node);
    for (int i = 0; i < n; ++i) 
    {
        if (graph[node][i] != INF) 
        {
            dist[i] = graph[node][i];
            prev[i] = node;
        }
    }
    while (s.size() != n) 
    {
        // 找到源节点到未在s中的节点的最短路径
        int minIdx = -1;
        int minDistance = -1;
        for (int i = 0; i < n; ++i) 
        {
            if (s.find(i) == s.end() && dist[i] != -1) 
            {
                if (minDistance == -1 || dist[i] < minDistance) 
                {
                    minIdx = i;
                    minDistance = dist[i];
                }
            }
        }
        // 剩下在集合中的节点都是集合S中不可达的，因此直接返回
        if (minIdx == -1) 
            break;
         s.insert(minIdx);
        // 借东风
        for (int i = 0; i < n; ++i) 
        {
            // minIdx与i邻接，并且从源点到minIdx再到i的最短路径更短，比源点到i更短
            if (graph[minIdx][i] != INF) 
            {
                if (dist[i] == -1 || dist[i] > dist[minIdx] + graph[minIdx][i]) 
                {
                    dist[i] = dist[minIdx] + graph[minIdx][i];
                    prev[i] = minIdx;
                    continue;
                }
            }
        }
    }
    return DijkstraResult{node, dist, prev};
}


int main(int argc, char const *argv[])
{
    vector<vector<int>> graph = 
    {
        {INF, 2, 5, INF, INF},
        {INF, INF, 2, 6, INF},
        {INF, INF, INF, 7, 1},
        {INF, INF, 2, INF, 4},
        {INF, INF, INF, INF, INF}
    };
    // 测试n次调用dijkstra来验证Floyd算法的结果
    for (int i = 0; i < graph.size(); ++i) 
    {
        DijkstraResult result = dijkstra(graph, i);
        vector<int>& dist = result.dist; 
        vector<int>& prev = result.prev;
        auto& node = result.node;
        printf("dist:");
        for (int i = 0; i < dist.size(); ++i) 
        {
            printf("%d ", dist[i]);
        }
        printf("\n");
        /*
        for (int i = 0; i < dist.size(); ++i) 
        {
            printf("%d -> %d: %d\n", node, i, dist[i]);
        }
        printf("prev:\n");
        for (int i = 0; i < prev.size(); ++i) 
        {
            printf("%d -> %d: %d\n", node, i, prev[i]);
        }
        */
    }
    return 0;
}
